// hard

// 给定一个整数数组nums， 再给定一个整数k，表示大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，我们只能看到滑动窗口内的k个数字，滑动窗口每次只能向右移动一位
// 要求返回滑动窗口中的最大值

// 单调队列
// 当滑动窗口右移时，我们需要把一个新的元素放入到队列中，为了保持队列的性质，我们不断将新的元素和队尾的元素比较，如果前者大于后者，那么队尾的元素就可以被永久的移除
// 我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素
//

// 时间复杂度： O(n)，n为数组nums的长度，每个下标恰好被放入队列一次，并且最多被弹出队列一次
// 空间复杂度：O(k)，队列使用的空间为O(k)

var maxSlidingWindow = function (nums, k) {
    let res = []
    let que = []
    for (let i = 0; i < nums.length; i++) {
        if (que.length === 0) {
            que.push(nums[i])
        } else {
            // 维护队列
            // 出队的两种情况：1. 队头元素不在窗口中（从队头出）， 2. 当前元素大于队尾元素（从队尾出）
            if (i - k >= 0 && nums[i - k] === que[0]) {
                // 当队头元素在窗口时，弹出
                que.shift()
            }
            // 当前元素若大于队尾元素，则移出，直到遇到小于小于的元素或者队列空了，进队
            while (que.length > 0 && nums[i] > que[que.length - 1]) {
                que.pop()
            }
            que.push(nums[i])
        }
        // 当滑动完k个元素之后开始提取队头元素
        if (i >= k - 1) {
            res.push(que[0])
        }
    }
    return res
}
let nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
console.log(maxSlidingWindow(nums, k));